package com.lun.easy;

import com.lun.util.BinaryTree.TreeNode;

public class TwoSumIVInputIsABST {

	public boolean findTarget(TreeNode root, int k) {
		return traverse(root, root, k);
	}

	// 前序遍历
	private boolean traverse(TreeNode node, TreeNode root, int k) {
		if (node == null)
			return false;

		// node.val恰好是k的一半时，根据BST特性，没必要找另一个节点
		if (2 * node.val != k && findTarget2(root, k - node.val))
			return true;

		return traverse(node.left, root, k) || traverse(node.right, root, k);
	}

	// 二分查找
	private boolean findTarget2(TreeNode node, int targetValue) {
		if (node == null)
			return false;

		if (node.val == targetValue)
			return true;

		return findTarget2(targetValue < node.val ? node.left : node.right, targetValue);
	}

}
